package basic.study.wantOffer.chapter5;

/**
 * @ClassName Problem54
 * @Description 二叉搜索树的第K个结点
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/12 17:04
 * @Version 1.0
 */
public class Problem54 {

    int index = 0;

    /**
     * 解法：中序遍历
     */
    public Node KthNode(Node root, int k) {
        if (root == null || k < 0) return null;
        Node pNode;
        pNode = getKthNode(root, k);
        return pNode;
    }

    private Node getKthNode(Node root, int k) {
        Node kthNode = null;
        Node node = getKthNode(root.left, k);
        if (node != null) {
            return node;
        }
        index++;
        if (index == k) {
            return root;
        }
        node = getKthNode(root.right, k);
        if (node != null) {
            return node;
        }
        return null;
    }

    class Node {
        Node left;
        Node right;
        int val;

        Node(int val) {
            this.val = val;
        }
    }
}
